package J3_12;

import java.util.HashSet;

public class test {

    //给出一个满足下述规则的二叉树：
    //
    //root.val == 0
    //如果 treeNode.val == x 且 treeNode.left != null，那么 treeNode.left.val == 2 * x + 1
    //如果 treeNode.val == x 且 treeNode.right != null，那么 treeNode.right.val == 2 * x + 2
    //现在这个二叉树受到「污染」，所有的 treeNode.val 都变成了 -1。
    //
    //请你先还原二叉树，然后实现 FindElements 类：
    //
    //FindElements(TreeNode* root) 用受污染的二叉树初始化对象，你需要先把它还原。
    //bool find(int target) 判断目标值 target 是否存在于还原后的二叉树中并返回结果。

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
        class FindElements {

            private HashSet<Integer> valSet;

            public FindElements(TreeNode root) {
                this.valSet = new HashSet<>();
                FindElementsS(root,0);
            }
            private void FindElementsS(TreeNode root, int x) {
                if (root == null) {
                    return;
                }
                root.val = x;
                valSet.add(x);
                FindElementsS(root.left, 2 * x + 1);
                FindElementsS(root.right, 2 * x + 2);
            }

            public boolean find(int target) {
                return valSet.contains(target);
            }
        }
  }
}
